Wireless Mesh and ad hoc networks are the environment of this invention. Wireless relaying is assumed to offer benefits such as easy and fast network deployment, low cost of installation and maintenance, flexibility, and scalability in both size and density. Coverage probability increases exponentially with the number of mesh nodes in the network.
Network resources are limited, including router (the network element that forwards packets) processing time and link throughput (e.g., bitrate). Users can easily overload certain networking resources making the network unusable, unless steps are taken to prevent this. There are number of ways in current internet protocol IP for congestion avoidance and traffic shaping. However, these approaches are generally targeted toward wireline Internet connections where energy consumption is not an issue. Further relevant background can be seen at: ENERGY EFFICIENT WIRELESS PACKET SCHEDULING AND FAIR QUEUING by Vijay Raghunathan, Saurabh Ganeriwal and Mani Srivistava; A RED BASED MINIMUM ENERGY ROUTING ALGORITHM FOR WIRELESS AD HOC NETWORKS by Xinyu Jin, Wenyu Cai, and Yu Zhang; RANDOM EARLY DETECTION GATEWAYS FOR CONGESTION AVOIDANCE by Sally Floyd and Van Jacobson; ENERGY-EFFICIENT TRANSMISSION OVER A WIRELESS LINK VIA LAZY PACKET SCHEDULING by Balaji Prabhakar, Elif Biyikoglu, and Abbas El Gamal; and LOW BIT-RATE VIDEO TRANSMISSION OVER FADING CHANNELS FOR WIRELESS MICROCELLULAR SYSTEMS by Masoud Khansari, Ahmad Jalali, Eric Dubois and Paul Mermelstein. Below are summarized some of these prior art IP approaches.
Lazy packet scheduling schemes try to find optimal transmission schedules for the packets so that energy consumption is minimized with respect to certain delay bounds. The inherent trade-off is delay versus energy consumption. These schemes are based on radio channel properties, i.e., decreased transmission rate lowers the energy consumed. Active queue management schemes delay packets in the router/relay node buffer as long as possible. FIG. 1A shows a graph of energy versus time for lazy packet scheduling, with time given by
      T    bit    =      1          b      ×              R        s            where b=bit rate and Rs=symbol rate; and energy given by
      E    bit    =                    C        s            ×                                    2            b                    -          1                b              +                  C        E            ×              1        b            where Cs and CE are constants. FIG. 1A clearly shows that transporting packets (bits) faster through the network is highly energy-intensive relative to slower relays.
The TCP (transmission control protocol) congestion avoidance algorithm approach is the primary basis for congestion control in the Internet. Various flavors of TCP are known in the art. Problems occur when many concurrent TCP flows are experiencing port queue buffer tail-drops (e.g., at interim/relaying TCP or UDP ports). The automatic congestion avoidance of TCP is therefore not enough. All flows that experience port queue buffer tail-drop will begin a TCP retrain at the same moment. This is called TCP global synchronization, and occurs when each sender reduces their transmission rate at the same time when packet loss occurs.
Random early detection (RED) is a queue management algorithm that also serves as a congestion avoidance algorithm. In the traditional tail drop algorithm, a router or other network component buffers as many packets as it can, and simply drops the ones it can't buffer. If buffers are constantly full, the network is congested. Tail drop (noted above) distributes buffer space unfairly among traffic flows. Tail drop can also lead to TCP global synchronization as all TCP connections “hold back” simultaneously, and then step forward simultaneously. Networks therefore alternate between being under-utilized and being flooded. RED addresses these issues by monitoring the average queue size and drops packets (or monitors marks when used in conjunction with explicit control notification ECN protocol) based on statistical probabilities. If a node's buffer is almost empty, all incoming packets are accepted. As the queue grows and the buffer becomes more filled, the probability for dropping an incoming packet grows also. When the buffer is full, the probability has reached 1 and all incoming packets are dropped.
FIG. 1B is a flow diagram showing the general concept of RED. At block 1B1, a packet is received at a relaying network node 1B2 such as a router. At block 1B3, an average queue length (e.g., average buffer occupancy) is computed. A comparison is made between that computed average queue length against a maximum queue length threshold and a minimum queue length threshold in order to calculate at block 1B4 a probability of dropping the packet. If the probability is not high that the packet will be dropped, then the packet is added to the queue at block 1B5. If instead the calculated drop probability is high, then at block 1B6 the packet is dropped.
RED is considered more “fair” than tail drop in that the more a host transmits, the more likely it is that its packets will be dropped. Early detection helps avoid global synchronization. Quality of service (QoS) differentiation (e.g., the probability of the network meeting a given traffic contract, or of a packet succeeding in passing between two points in the network within its desired latency period) is not seen possible in RED.
Weighted RED (WRED) and RED In/Out (RIO) provide early detection with some QoS considerations. WRED is an extension to (basic) RED, where different queues may have different buffer occupation thresholds before random dropping starts (and different dropping probabilities) and packets are classified into these queues according to priority information so as to enable some DoS differentiation and some DiffServ capability (e.g., packets placed in queues with higher buffer occupation thresholds or lower dropping probabilities are effectively prioritized). WRED generally drops packets selectively based on IP precedence. Packets with a higher IP precedence are less likely to be dropped than packets with a lower precedence given the disparate buffer occupation thresholds. Thus, higher priority traffic is delivered with a higher probability than lower priority traffic. However, WRED may also be configured to ignore IP precedence when making drop decisions so that non-weighted RED behavior is achieved. WRED is useful on any output interface where congestion might be expected, but WRED is typically used in the core routers of a network rather than at the edge where the IP network interfaces with another network operating with different protocol (e.g., wireless cellular, WLAN, etc.). Edge routers assign IP precedence to packets as they enter the IP network. WRED uses these precedences to determine how it treats different types of traffic, but WRED is seen as overly complex, especially for networks such as ad hoc that do not use a predefined infrastructure.
IP Explicit Congestion Notification (ECN) is only used when the two hosts signal that they want to use it. With this method, an ECN bit is used to signal that there is explicit congestion. This is better in some instances than the indirect packet delete congestion notification performed by the RED/WRED algorithms, but it requires explicit support by both hosts to be effective. Some outdated or buggy network equipment that does not support ECN have been known to drop packets that have the ECN bit set, rather than ignoring the bit. When a router receives a packet marked as ECN capable and anticipates congestion (e.g., using RED), it will set a flag notifying the sender to decrease its window size (sending rate). The intent is to avoid that sender resending packets that would add further congestion.
What is needed in the art is a more elegant method and apparatus for packet scheduling that is designed to meet the needs of wireless mesh networks. The solution described herein has broad applications for any such mesh network, but are particularly advantageous to address specific limitations inherent in wireless networks.